The city traffic
network consists of n nodes numbered
from 1 to n and m one-way roads connecting pairs of nodes. In order to reduce the
length of the shortest path between two different critical nodes s and t, a list of k two-way
roads are proposed as candidates to be constructed. Your task is to write a
program to choose one two-way road from the proposed list in order to minimize
the resulting shortest path between s
and t.
Input. Consists of
several data sets. The first line contains the number of data sets which is a
positive integer and is not bigger than 20. The following lines describe the
data sets.
For each data
set, the first line contains five positive integers n (n ≤ 10 000), m (m
≤ 100 000), k (k < 300), s (1 ≤ s ≤ n), t
(1 ≤ t ≤ n) separated by space. The i-th line of the following m lines contains three integers di, ci, li
separated by space, representing the length li
( 0< li ≤ 1000)
of the i-th one-way road connecting node di to ci. The j-th line of the
next k lines contains three positive
integers uj, vj and qj (qj
≤ 1000) separated by space, representing the j-th proposed
two-way road of length qj
connecting node uj to vj.
Output. For each data
set, write on one line the smallest possible length of the shortest path after
building the chosen one two-way road from the proposed list. In case, there
does not exist a path from s to t, write -1.
|
Sample
input |
Sample
output |
|
1 4 5 3 1 4 1 2 13 2 3 19 3 1 25 3 4 17 4 1 18 1 3 23 2 3 5 2 4 25 |
35 |
РЕШЕНИЕ
алгоритм Дейкстры
Анализ алгоритма
Задан ориентированный взвешенный граф. Вам следует добавить
одну из возможных k дорог так чтобы минимизировать
кратчайший путь между вершинами s и t.
Запустим алгоритм Дейкстры из вершины s и из вершины t. Пусть dist[i] содержит кратчайшее
расстояние от s до i, а
distR[i] содержит кратчайшее расстояние от t до i. Тогда при добавлении ребра (b, e) весом w длина
пути между s и t может
уменьшится до dist[b] + w + distR[e] либо до dist[e] + w + distR[b].
Пусть res = dist[t] – длина кратчайшего пути между s и t в исходном
графе. Далее следует перебрать каждую из допустимых на добавление дорогу (b, e) весом w и найти
min(res, dist[b] + w + distR[e], dist[e] + w + distR[b])
Поскольку n ≤ 105,
то при реализации алгоритма Дейкстры следует воспользоваться очередью с приоритетами.
Реализация алгоритма
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#define MAX 10010
#define INF 0x3F3F3F3F
using namespace std;
int tests, i, j, d, n, m, s, k, t, b, e, w, res;
int used[MAX], dist[MAX], distR[MAX];
struct edge
{
int node, dist;
edge(int node, int
dist) : node(node), dist(dist) {}
};
bool operator< (edge a, edge
b)
{
return a.dist > b.dist;
}
int min(int i, int j)
{
return (i < j) ? i : j;
}
vector<vector<edge> > g, gr;
void Dijkstra(vector<vector<edge> > &g, int *d, int start)
{
int v, to, cost;
memset(used,0,sizeof(used));
priority_queue<edge> pq;
pq.push(edge(start,0));
while(!pq.empty())
{
edge e = pq.top(); pq.pop();
v = e.node;
if (e.dist > d[v]) continue;
for(j = 0; j < g[v].size(); j++)
{
to = g[v][j].node;
cost = g[v][j].dist;
if (!used[to] && (d[to] >
d[v] + cost))
{
d[to] = d[v] + cost;
pq.push(edge(to,d[to]));
}
}
}
}
int main(void)
{
scanf("%d",&tests);
while(tests--)
{
scanf("%d %d %d %d %d",&n,&m,&k,&s,&t);
g.clear(); g.resize(n+1);
gr.clear();gr.resize(n+1);
for(i = 0; i < m; i++)
{
scanf("%d %d %d",&b,&e,&w);
g[b].push_back(edge(e,w));
gr[e].push_back(edge(b,w));
}
memset(dist,0x3F,sizeof(dist));
dist[s] = 0;
memset(distR,0x3F,sizeof(distR));
distR[t] = 0;
Dijkstra(g,dist,s);
Dijkstra(gr,distR,t);
res = dist[t];
for(i = 0; i < k; i++)
{
scanf("%d %d %d",&b,&e,&w);
res = min(res, dist[b] + w + distR[e]);
res = min(res, dist[e] + w + distR[b]);
}
if (res == INF)
printf("-1\n");
else
printf("%d\n",res);
}
return 0;
}